package com.chenken;

/**
 *AVL�� 
 *
 */
public class AVLTree<E> extends BinarySearchTree<E>{

	@Override
	protected Node<E> createNewNode(E element,Node<E> parent) {
		return new AVLNode<E>(element, parent);
	}
	
	@Override
	protected void afterAdd(Node<E> node) {
		while((node = node.parent)!=null) {
			if(isBalanced(node)) {
				//	更新高度
				updateHeight(node);
			}else {
				// 	恢复平衡
				rebalance(node);
				break;
			}
		}
	}
	
	@Override
	protected void afterRemove(Node<E> node) {
		while((node = node.parent)!=null) {
			if(isBalanced(node)) {
				//	更新高度
				updateHeight(node);
			}else {
				//	恢复平衡
				rebalance(node);
			}
		}
	}
	
	private boolean isBalanced(Node<E> node) {
		AVLNode<E> avlNode = (AVLNode<E>)node;
		return Math.abs(avlNode.balanceFactor()) <= 1;
	}
	
	private void updateHeight(Node<E> node) {
		AVLNode<E> avlNode = (AVLNode<E>)node;
		avlNode.updateHeight();
	}
	
	private void rebalance(Node<E> grand) {
		Node<E> parent = ((AVLNode<E>)grand).tallerNode();
		Node<E> node = ((AVLNode<E>)parent).tallerNode();
		
		if(parent.isLeftChild()) {
			if(node.isLeftChild()) { //LL
				rotateRight(grand);
			}else {					//LR
				rotateLeft(parent);
				rotateRight(grand);
			}
		}else {
			if(node.isLeftChild()) { //RL
				rotateRight(parent);
				rotateLeft(grand);
			}else {					//RR
				rotateLeft(grand);
			}
		}
	}
	
	/**
	 * 左旋转
	 * @param grand
	 */
	private void rotateLeft(Node<E> grand) {
		Node<E> parent = grand.right;
		
		Node<E> pLeftChild = parent.left;
		grand.right = pLeftChild;
		parent.left = grand;
		
		afterRotate(grand, parent, pLeftChild);
	}
	
	/**
	 * 右旋转
	 * @param grand
	 */
	private void rotateRight(Node<E> grand) {
		Node<E> parent = grand.left;
		
		Node<E> pRightChild = parent.right;
		grand.left = pRightChild;
		parent.right = grand;
		
		afterRotate(grand, parent, pRightChild);
	}

	private void afterRotate(Node<E> grand, Node<E> parent, Node<E> pRightChild) {
		// 	让parent称为子树的根节点
		parent.parent = grand.parent;
		if(grand.isLeftChild()) {
			grand.parent.left = parent;
		}else if(grand.isRightChild()) {
			grand.parent.right = parent;
		}else {
			root = parent;
		}
		// 	更新child的parent
		if(pRightChild != null ) {
			pRightChild.parent = grand;
		}
		// 	更新grand的parent
		grand.parent = parent;
		// 	更新高度
		updateHeight(grand);
		updateHeight(parent);
	}
	
	private static class AVLNode<E> extends Node<E>{
		
		int height = 1;
		
		public AVLNode(E element, Node<E> parent) {
			super(element, parent);
		}
		
		public int balanceFactor() {
			int leftHeight = left == null?0:((AVLNode<E>)left).height;
			int rightHeight = right == null?0:((AVLNode<E>)right).height;
			return leftHeight - rightHeight;
		}
		
		public void updateHeight() {
			int leftHeight = left == null?0:((AVLNode<E>)left).height;
			int rightHeight = right == null?0:((AVLNode<E>)right).height;
			height = 1+ Math.max(leftHeight, rightHeight);
		}
		
		public Node<E> tallerNode(){
			int leftHeight = left == null?0:((AVLNode<E>)left).height;
			int rightHeight = right == null?0:((AVLNode<E>)right).height;
			if(leftHeight > rightHeight) { return left; }
			if(leftHeight < rightHeight) { return right; }
			return isLeftChild() ? left : right;
		}
	}

}
